#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution1 {
public:
    int maxOperations(vector<int>& nums) {
        int res = 1; int n = nums.size();
        int num = nums[0] + nums[1];
        for (int i = 2; i < n - 1; i += 2)
        {
            if (nums[i] + nums[i + 1] != num)
                break;
            res++;
        }
        return res;
    }
};

class Solution2 {
public:
    int memo[2001][2001];

    int dfs(vector<int>& nums, int left, int right, int num)
    {
        if (left >= right) return 0;
        if (memo[left][right] != -1) return memo[left][right];
        int ans = 0;
        if (nums[left] + nums[left + 1] == num)
        {
            ans = max(1 + dfs(nums, left + 2, right, num), ans);
        }
        if (nums[right] + nums[right - 1] == num)
        {
            ans = max(1 + dfs(nums, left, right - 2, num), ans);
        }
        if (nums[left] + nums[right] == num)
        {
            ans = max(1 + dfs(nums, left + 1, right - 1, num), ans);
        }
        return memo[left][right] = ans;
    }

    int maxOperations(vector<int>& nums) {
        memset(memo, -1, sizeof(memo));
        int n = nums.size();
        int ans = 1 + dfs(nums, 2, n - 1, nums[0] + nums[1]);
        ans = max(ans, 1 + dfs(nums, 0, n - 3, nums[n - 1] + nums[n - 2]));
        ans = max(ans, 1 + dfs(nums, 1, n - 2, nums[0] + nums[n - 1]));
        return ans;
    }
};

class Solution3 {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<int> arr(n + 2, 1);
        for (int i = 0; i < n; ++i) {
            arr[i + 1] = nums[i];
        }

        vector<vector<int>> f(n + 2, vector<int>(n + 2, 0));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 2; j <= n + 1; ++j) {
                for (int k = i + 1; k < j; ++k) {
                    f[i][j] = max(f[i][j], f[i][k] + f[k][j] + arr[i] * arr[k] * arr[j]);
                }
            }
        }
        return f[0][n + 1];
    }
};

class Solution4 {
public:
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };

    int countBattleships(vector<vector<char>>& board) {
        int m = board.size(); int n = board[0].size();
        function<void(int, int)> dfs = [&](int i, int j) {
            for (int k = 0; k < 4; ++k)
            {
                int x = i + dx[k]; int y = j + dy[k];
                if (x >= 0 && y >= 0 && x < m && y < n && board[x][y] == 'X')
                {
                    board[x][y] = '.';
                    dfs(x, y);
                }
            }
        };
        int cnt = 0;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
            {
                if (board[i][j] == 'X')
                {
                    ++cnt;
                    dfs(i, j);
                }
            }
        return cnt;
    }
};

class Solution5 {
public:
    int findLUSlength(string a, string b) {
        return a != b ? max(a.length(), b.length()) : -1;
    }
};

class Solution6 {
public:
    int findLUSlength(vector<string>& strs) {
        int res = -1;
        int n = strs.size();
        auto check = [](const string& s, const string& t) {
            int ss = s.size(), ts = t.size();
            int j = 0;
            for (int i = 0; i < ts && j < ss; ++i)
            {
                if (t[i] == s[j])
                    ++j;
            }
            return j == ss;
        };

        for (int i = 0; i < n; ++i)
        {
            int cur = strs[i].size();
            for (int j = 0; j < n; ++j)
            {
                if (i != j && check(strs[i], strs[j]))
                {
                    cur = -1;
                    break;
                }
            }
            res = max(res, cur);
        }

        return res;
    }
};

int main()
{

	return 0;
}